package org.meichao.demo.service.algorithms;

import java.util.HashMap;

/**
 * LRU算法
 */
public class LRUCache {

    private Node head,tail;
    private int limit;
    private HashMap<String,Node> nodeHashMap;

    public LRUCache(int limit) {
        this.limit = limit;
        nodeHashMap = new HashMap<>();
    }

    /**
     * 添加node到尾部
     * @param node
     */
    public void addNode(Node node){
        if(tail != null){
            tail.next = node;
            node.pre = tail;
            node.next = null;
        }
        tail = node;
        if(head == null){
            head = node;
        }
    }

    /**
     * 删除头部节点
     * @param node
     */
    public String removeNode(Node node){
        if(node == tail){
            //移除尾节点
            tail = tail.pre;
        }else if(node == head){
            //移除头节点
            head = head.next;
        }else{
            //移除中间节点
            node.pre.next = node.next;
            node.next.pre = node.pre;
        }
        return node.key;
    }

    /**
     * 刷新存在node节点的位置
     * @param node
     */
    public void refreshNode(Node node){
        //如果访问的是尾节点，不用移动
        if(node == tail){
            return;
        }
        //删除节点
        removeNode(node);
        //插入节点
        addNode(node);
    }

    public void removeMap(String key){
        //Node node = nodeHashMap.get(key);
        //removeNode(node);
        nodeHashMap.remove(key);
    }

    /**
     *  将节点加入到尾结点，如果容量已满，将会删除头结点
     * @param key
     * @param value
     */
    public void put(String key,String value){
        Node node = nodeHashMap.get(key);
        //node不存在
        if(node == null){
            //超过大小限制，去除头节点
            if(nodeHashMap.size() >= limit){
                String headKey = removeNode(head);
                removeMap(headKey);
            }
            node = new Node(key, value);
            addNode(node);
            nodeHashMap.put(key, node);
        }

    }

    /**
     * 如果节点不存在，返回null.如果存在，将节点移动到尾部结点，并返回节点的数据。
     * @param key
     * @return
     */
    public String get(String key){
        Node node = nodeHashMap.get(key);
        if(node == null){
            return null;
        }
        refreshNode(node);
        return node.value;
    }

    /**
     * node类
     */
    class Node{
        private Node pre;
        private Node next;
        private String key;
        private String value;

        public Node(String key, String value) {
            this.key = key;
            this.value = value;
        }
    }

    public static void main(String[] args) {

        LRUCache lruCache = new LRUCache(5);
        lruCache.put("001","1");
        lruCache.put("002","2");
        lruCache.put("003","3");
        lruCache.put("004","4");
        lruCache.put("005","5");
        lruCache.put("006","6");
        lruCache.put("007","7");
        System.out.println(lruCache.get("002"));
        System.out.println(lruCache.get("007"));

    }
}
